from collections import deque
from typing import List


class Solution:
    """
    方法： maxSlidingWindow
    逻辑: 使用双端队列维护当前窗口中的最大值索引，通过维护一个单调递减队列来快速获取每个窗口的最大值

    Args:
        nums: 整数数组
        k: 滑动窗口大小

    Returns:
        List[int]: 每个滑动窗口的最大值组成的数组

    Time: O(n) - 每个元素最多入队和出队一次
    Space: O(k) - 双端队列最多存储k个元素
    """
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []
        q = deque()
        for i, x in enumerate(nums):
            while q and nums[q[-1]] <= x:
                q.pop()
            q.append(i)
            if i - q[0] >= k:
                q.popleft()
            if i >= k-1:
                ans.append(nums[q[0]])
        return ans